//A trie (pronounced as "try") or prefix tree is a tree data structure used to e
//fficiently store and retrieve keys in a dataset of strings. There are various ap
//plications of this data structure, such as autocomplete and spellchecker. 
//
// Implement the Trie class: 
//
// 
// Trie() Initializes the trie object. 
// void insert(String word) Inserts the string word into the trie. 
// boolean search(String word) Returns true if the string word is in the trie (i
//.e., was inserted before), and false otherwise. 
// boolean startsWith(String prefix) Returns true if there is a previously inser
//ted string word that has the prefix prefix, and false otherwise. 
// 
//
// 
// Example 1: 
//
// 
//Input
//["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
//[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
//Output
//[null, null, true, false, true, null, true]
//
//Explanation
//Trie trie = new Trie();
//trie.insert("apple");
//trie.search("apple");   // return True
//trie.search("app");     // return False
//trie.startsWith("app"); // return True
//trie.insert("app");
//trie.search("app");     // return True
// 
//
// 
// Constraints: 
//
// 
// 1 <= word.length, prefix.length <= 2000 
// word and prefix consist only of lowercase English letters. 
// At most 3 * 104 calls in total will be made to insert, search, and startsWith
//. 
// 
// Related Topics 设计 字典树 哈希表 字符串 
// 👍 892 👎 0


package leetcode.editor.cn;

//Java：Implement Trie (Prefix Tree)
class P208ImplementTriePrefixTree {
    public static void main(String[] args) {
        Trie solution = new P208ImplementTriePrefixTree().new Trie();
        // TO TEST
        solution.insert("apple");
        solution.search("apple");
        solution.search("app");
        solution.startsWith("app");
        solution.insert("app");
        solution.search("app");

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Trie {
        int R = 256;
        Node alph;

        /**
         * Initialize your data structure here.
         */
        public Trie() {
            alph = new Node();

        }

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            char[] chars = word.toCharArray();
            Node[] child = alph.getChild();
            Node[] preChild = child;
            Node node = null;
            for (char c : chars) {
                node = preChild[(int) c];
                if (node == null) {
                    node = new Node();
                }
                preChild[(int) c] = node;
                preChild = node.getChild();
            }
            node.setC(word);
        }

        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            char[] chars = word.toCharArray();
            Node[] child = alph.getChild();
            Node[] preChild = child;
            Node node = null;
            for (char c : chars) {
                node = preChild[(int) c];
                if (node == null) {
                    return false;
                } else {
                    preChild = node.getChild();
                }
            }
            return word.equals(node.getC());
        }

        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            char[] chars = prefix.toCharArray();
            Node[] child = alph.getChild();
            Node[] preChild = child;

            for (char c : chars) {
                Node node = preChild[(int) c];
                if (node == null) {
                    return false;
                } else {
                    preChild = node.getChild();
                }
            }
            return true;
        }

        class Node<Value> {
            Node[] child = new Node[256];
            Value c;

            public Node[] getChild() {
                return child;
            }

            public void setChild(Node[] child) {
                this.child = child;
            }

            public Value getC() {
                return c;
            }

            public void setC(Value c) {
                this.c = c;
            }
        }
    }

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */
//leetcode submit region end(Prohibit modification and deletion)

}